package org.example.myleet.p444;

import java.util.*;

public class Solution {
    public boolean sequenceReconstruction(int[] nums, int[][] sequences) {
        int n = nums.length;
        Node[] nodes = new Node[n + 1];
        //利用sequence重塑点与点的先后顺序拓扑图，排在前面的记为parent，排在后面的记为child
        for (int[] sequence : sequences) {
            if (sequence.length > 1) {
                for (int i = 0; i < sequence.length - 1; ++i) {
                    int i2 = i + 1;
                    if (null == nodes[sequence[i]]) {
                        nodes[sequence[i]] = new Node(sequence[i]);
                    }
                    if (null == nodes[sequence[i2]]) {
                        nodes[sequence[i2]] = new Node(sequence[i2]);
                    }
                    nodes[sequence[i]].children.add(sequence[i2]);
                    nodes[sequence[i2]].parents.add(sequence[i]);
                }
            } else {
                if (null == nodes[sequence[0]]) {
                    nodes[sequence[0]] = new Node(sequence[0]);
                }
            }
        }
        //下面利用队列进行拓扑排序，不断地寻找出度为0的节点（children为0）加入队列中以重塑原序列
        List<Integer> res = new LinkedList<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; ++i) {
            if (null != nodes[i] && 0 == nodes[i].children.size()) {
                queue.add(i);
            }
        }
        if (queue.isEmpty()) {
            return false;
        }
        while (!queue.isEmpty()) {
            if (queue.size() != 1) {
                return false;
            }
            //从队列中拿到上一个出度为0的节点，作为序列的结尾
            Node node = nodes[queue.poll()];
            res.add(0, node.i);
            for (int parent : node.parents) {
                nodes[parent].children.remove(node.i);
                if (0 == nodes[parent].children.size()) {
                    //找到出度为0的节点，加入队列用于在下一个循环中用于拓扑排序
                    if (queue.size() > 0) {
                        return false;
                    }
                    queue.add(parent);
                }
            }
        }
        if (res.size() != n) {
            return false;
        }
        int i = 0;
        for (int r : res) {
            if (r != nums[i]) {
                return false;
            }
            ++i;
        }
        return true;
    }

    static class Node {
        int i;
        Set<Integer> children;
        Set<Integer> parents;

        public Node(int i) {
            this.i = i;
            children = new HashSet<>();
            parents = new HashSet<>();
        }
    }
}
